class Solution
{
private:
    bool row[9][10] = { 0 };
    bool col[9][10] = { 0 };
    bool gird[3][3][10] = { 0 };
    bool flag = 0;
public:
    bool IsOk(vector<vector<char>>& board, int m, int n, int ins)
    {
        return row[m][ins] == 0 && col[n][ins] == 0 && gird[m / 3][n / 3][ins] == 0;
    }

    bool ToTrueNum(vector<vector<char>>& board, int& m, int& n)
    {
        if (n == 9)
        {
            n = 0;
            m++;
        }
        while (m < 9 && n < 9 && board[m][n] != '.')
        {
            n++;
            if (n == 9)
            {
                n = 0;
                m++;
            }
        }

        if (m == 9)
        {
            flag = 1;
            //ret = board;
            return 1;
        }
        return 0;
    }

    void dfs(vector<vector<char>>& board, int m, int n)
    {
        if (flag) return;
        if (ToTrueNum(board, m, n)) return;

        for (int i = 1; i <= 9; i++)
        {
            if (board[m][n] == '.' && IsOk(board, m, n, i))
            {
                row[m][i] = col[n][i] = gird[m / 3][n / 3][i] = 1;
                board[m][n] = '0' + i;
                dfs(board, m, n + 1);
                if (flag) return;
                row[m][i] = col[n][i] = gird[m / 3][n / 3][i] = 0;
                board[m][n] = '.';
            }
        }
    }

    void AddToBoard(vector<vector<char>>& board)
    {
        for (int i = 0; i < 9; i++)
            for (int j = 0; j < 9; j++)
            {
                int ch = board[i][j];
                if (ch >= '0')
                {
                    ch -= '0';
                    row[i][ch] = col[j][ch] = gird[i / 3][j / 3][ch] = 1;
                }
            }
    }

    void solveSudoku(vector<vector<char>>& board)
    {
        AddToBoard(board);
        dfs(board, 0, 0);
        //board = ret;
    }

    //vector<vector<char>> ret;
};
